﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Globalization;

namespace ArgusPCLib.Mathematics
{
	public class Integer : ILinearScalar
	{
		#region Static
		#region Fields
		const int ExponentMask = (int)(~0u >> 1);
		public const int MaxExponent = ExponentMask;
		public const int MinExponent = 0;
		public const int Base = ~0;
		#endregion

		#region Properties
		public static int WordSize { get { return BitManager.WordSize; } }
		public static Integer Zero { get { return new Integer(0); } }
		public static Integer One { get { return new Integer(1); } }

		static Integer Base10 { get { return new Integer(1000000000); } }
		const int Base10DigitLength = 9;
		#endregion

		#region Constructors
		static Integer()
		{

		}
		#endregion

		#region Methods
		#region Private
		static bool Sort(Integer a, Integer b, out BitManager max, out BitManager min, out long exponent)
		{
			BitManager bmA = a.bitManager;
			BitManager bmB = b.bitManager;
			exponent = a.exponent;
			if (a.exponent > b.exponent)
			{
				bmA = new BitManager(bmA);
				bmA.LLS((int)(a.exponent - b.exponent)*BitManager.WordSize);
				exponent = b.exponent;
			}
			else if (a.exponent < b.exponent)
			{
				bmB = new BitManager(bmB);
				bmB.LLS((int)(b.exponent - a.exponent) * BitManager.WordSize);
				exponent = a.exponent;
			}

			if (bmA > bmB)
			{
				if (object.ReferenceEquals(bmA, a.bitManager))
					max = new BitManager(bmA);
				else
					max = bmA;
				min = bmB;
				return true;
			}
			else
			{
				if (object.ReferenceEquals(bmB, b.bitManager))
					max = new BitManager(bmB);
				else
					max = bmB;
				min = bmA;
				return false;
			}
		}
		#endregion

		#region Various
		public static bool GetSign(Integer integer) { return integer.isNegative; }
		public static WordCollection GetSignificant(Integer integer) { return new WordCollection(integer); }
		public static BitCollection GetSignificantBits(Integer integer) { return new BitCollection(integer); }
		public static int GetExponent(Integer integer) { return (int)integer.exponent; }
		#endregion

		#region Math
		public static Integer Negate(Integer integer)
		{
			Integer RetVal = new Integer(integer);
			RetVal.isNegative = !integer.isNegative;
			return RetVal;
		}

		public static Integer Abs(Integer integer)
		{
			if (integer.isNegative)
				return Integer.Negate(integer);
			return integer;
		}

		public static Integer Divide(Integer dividend, Integer divisor, out Integer remainder)
		{
			if (divisor == 0)
				throw new DivideByZeroException();
			if (dividend.exponent > dividend.exponent)
			{
				remainder = new Integer(dividend);
				return Integer.Zero;
			}

			BitManager bits = new BitManager(dividend.bitManager);
			if (dividend.exponent > dividend.exponent)
			{
				bits.LLS((int)(dividend.exponent - dividend.exponent) * BitManager.WordSize);
			}
			BitManager r;
			bits.Divide(divisor.bitManager, out r);
			Integer RetVal = new Integer(bits, false, true);
			remainder = new Integer(r, false, true);
			RetVal.isNegative = dividend.isNegative != divisor.isNegative;
			remainder.isNegative = RetVal.isNegative;
			return RetVal;
		}

		public static Integer Power(Integer b, int e)
		{
			Integer result = 1;
			Integer a = new Integer(b);
			uint E = (uint)System.Math.Abs(e);
			if ((E & 1u) == 1u)
				result.isNegative = b.isNegative;
			result.exponent = b.exponent * e;
			while (E > 0)
			{
				if ((E & 1) == 1)
					result.bitManager.Multiply(a.bitManager);
				a.bitManager.Multiply(a.bitManager);
				E >>= 1;
			}

			if (e < 0)
				result = 1 / result;

			result.TrimTrailingWords();
			return result;
		}

		/// <summary>
		/// Returns the greatest common divisor.
		/// </summary>
		public static Integer GCD(Integer a, Integer b)
		{
			BitManager bmA = new BitManager(a.bitManager);
			BitManager bmB = new BitManager(b.bitManager);
			int exponent = System.Math.Min(a.exponent, b.exponent);
			if (a.exponent < b.exponent)
				bmB.LLS((int)(b.exponent - a.exponent) * BitManager.WordSize);
			else if (a.exponent > b.exponent)
				bmA.LLS((int)(a.exponent - b.exponent) * BitManager.WordSize);

			while (bmB > 0)
			{
				BitManager r;
				bmA.Divide(bmB, out r);
				bmA = bmB;
				bmB = r;
			}
			Integer RetVal = new Integer(bmA, false, true);
			RetVal.exponent = exponent;
			return RetVal;
		}

		/// <summary>
		/// Returns the least common multiply.
		/// </summary>
		public static Integer LCM(Integer a, Integer b)
		{
			if (a == 0 && b == 0)
				return 0;
			Integer RetVal = a * b;
			RetVal.isNegative = false;
			Integer gcd = Integer.GCD(a, b);
			BitManager r;
			RetVal.bitManager.Divide(gcd.bitManager, out r);
			RetVal.exponent -= gcd.exponent;
			return RetVal;
		}
		#endregion

		#region Operators
		#region Comparison
		public static bool operator ==(Integer a, int b)
		{
			if (a.isNegative != (b < 0) || a.exponent != 0)
				return false;
			return a.bitManager == System.Math.Abs(b);
		}

		public static bool operator ==(Integer a, Integer b)
		{
			if (object.ReferenceEquals(a, null) || object.ReferenceEquals(b, null))
				return object.ReferenceEquals(a, b);

			if (a.signAndExponent != b.signAndExponent)
				return false;

			return a.bitManager == b.bitManager;
		}

		public static bool operator !=(Integer a, int b)
		{
			return !(a == b);
		}

		public static bool operator !=(Integer a, Integer b)
		{
			return !(a == b);
		}

		public static bool operator <(Integer a, int b)
		{
			if (a.isNegative != (b < 0))
				return a.isNegative;

			if (a.exponent > 0)
				return a.isNegative;
			else if (a.isNegative)
				return a.bitManager > System.Math.Abs(b);
			else
				return a.bitManager < b;
		}

		public static bool operator <(Integer a, Integer b)
		{
			if (a.isNegative != b.isNegative)
				return a.isNegative;

			if (a.exponent < b.exponent)
				return !a.isNegative;
			else if (a.exponent > b.exponent)
				return a.isNegative;
			else if (a.isNegative)
				return a.bitManager > b.bitManager;
			else
				return a.bitManager < b.bitManager;
		}

		public static bool operator >(Integer a, int b)
		{
			if (a.isNegative != (b < 0))
				return !a.isNegative;

			if (a.exponent > 0)
				return !a.isNegative;
			else if (a.isNegative)
				return a.bitManager < System.Math.Abs(b);
			else
				return a.bitManager > b;
		}

		public static bool operator >(Integer a, Integer b)
		{
			if (a.isNegative != b.isNegative)
				return !a.isNegative;

			if (a.exponent < b.exponent)
				return a.isNegative;
			else if (a.exponent > b.exponent)
				return !a.isNegative;
			else if (a.isNegative)
				return a.bitManager < b.bitManager;
			else
				return a.bitManager > b.bitManager;
		}

		public static bool operator <=(Integer a, Integer b)
		{
			return (a < b || a == b);
		}

		public static bool operator >=(Integer a, Integer b)
		{
			return (a > b || a == b);
		}

		public static bool operator <=(Integer a, int b)
		{
			return (a < b || a == b);
		}

		public static bool operator >=(Integer a, int b)
		{
			return (a > b || a == b);
		}
		#endregion

		#region Bitwise Operations
		//public static Integer operator ~(Integer integer)
		//{
		//	Integer RetVal = new Integer(integer);
		//	RetVal.isNegative = !integer.isNegative;
		//	RetVal.bitManager.BitwiseNot();
		//	RetVal.bitManager.TrimLeadingWords();
		//	return RetVal;
		//}

		//public static Integer operator &(Integer a, Integer b)
		//{
		//	Integer RetVal = new Integer(a);
		//	RetVal.isNegative = a.isNegative && b.isNegative;
		//	RetVal.bitManager.BitwiseAnd(b.bitManager);
		//	RetVal.bitManager.TrimLeadingWords();
		//	return RetVal;
		//}

		//public static Integer operator |(Integer a, Integer b)
		//{
		//	Integer RetVal = new Integer(a);
		//	RetVal.isNegative = a.isNegative || b.isNegative;
		//	RetVal.bitManager.BitwiseOr(b.bitManager);
		//	RetVal.bitManager.TrimLeadingWords();
		//	return RetVal;
		//}

		//public static Integer operator ^(Integer a, Integer b)
		//{
		//	Integer RetVal = new Integer(a);
		//	RetVal.isNegative = a.isNegative != b.isNegative;
		//	RetVal.bitManager.BitwiseXor(b.bitManager);
		//	RetVal.bitManager.TrimLeadingWords();
		//	return RetVal;
		//}

		public static Integer operator <<(Integer integer, int count)
		{
			Integer RetVal = new Integer(integer);
			RetVal.bitManager.LLS(count);
			RetVal.TrimTrailingWords();
			return RetVal;
		}

		public static Integer operator >>(Integer integer, int count)
		{
			Integer RetVal = new Integer(integer);
			RetVal.bitManager.LRS(count);
			RetVal.bitManager.TrimLeadingWords();
			return RetVal;
		}
		#endregion

		#region Math Operations
		public static Integer operator -(Integer i)
		{
			return Integer.Negate(i);
		}

		public static Integer operator ++(Integer i)
		{
			Integer RetVal = new Integer(i);
			RetVal.Increment();
			return RetVal;
		}

		public static Integer operator --(Integer i)
		{
			Integer RetVal = new Integer(i);
			RetVal.Decrement();
			return RetVal;
		}

		public static Integer operator +(Integer a, int b)
		{
			Integer RetVal;
			bool bIsNegative = b < 0;
			b = System.Math.Abs(b);
			if (a.isNegative == bIsNegative)
			{
				BitManager bits = new BitManager(a.bitManager);
				if (a.exponent > 0)
					bits.LLS((int)a.exponent * BitManager.WordSize);
				bits.Add(b);
				RetVal = new Integer(bits, false, true);
				RetVal.isNegative = a.isNegative;
			}
			else if (a == b)
			{
				return Integer.Zero;
			}
			else if (a > b)
			{
				BitManager bits = new BitManager(a.bitManager);
				if (a.exponent > 0)
					bits.LLS((int)a.exponent * BitManager.WordSize);
				bits.Subtract(b);
				RetVal = new Integer(bits, false, true);
				RetVal.isNegative = a.isNegative;
			}
			else
			{
				BitManager bits = new BitManager(1);
				bits[0] = b;
				bits.Subtract(a.bitManager);
				RetVal = new Integer(bits, false, true);
				RetVal.isNegative = !a.isNegative;
			}
			return RetVal;
		}

		public static Integer operator +(Integer a, long b)
		{
			Integer RetVal;
			bool bIsNegative = b < 0;
			b = System.Math.Abs(b);
			if (a.isNegative == bIsNegative)
			{
				BitManager bits = new BitManager(a.bitManager);
				if (a.exponent > 0)
					bits.LLS((int)a.exponent * BitManager.WordSize);
				bits.Add(b);
				RetVal = new Integer(bits, false, true);
				RetVal.isNegative = a.isNegative;
			}
			else if (a == b)
			{
				return Integer.Zero;
			}
			else if (a > b)
			{
				BitManager bits = new BitManager(a.bitManager);
				if (a.exponent > 0)
					bits.LLS((int)a.exponent * BitManager.WordSize);
				bits.Subtract(b);
				RetVal = new Integer(bits, false, true);
				RetVal.isNegative = a.isNegative;
			}
			else
			{
				BitManager bits = new BitManager(2);
				bits.Add(b);
				bits.Subtract(a.bitManager);
				RetVal = new Integer(bits, false, true);
				RetVal.isNegative = !a.isNegative;
			}
			return RetVal;
		}

		public static Integer operator +(Integer a, Integer b)
		{
			BitManager max, min;
			long exponent;
			bool order = Integer.Sort(a, b, out max, out min, out exponent);

			Integer RetVal;
			if (a.isNegative == b.isNegative)
			{
				max.Add(min);
				RetVal = new Integer(max, false, true);
				RetVal.isNegative = a.isNegative;
			}
			else if (max == min)
			{
				return Integer.Zero;
			}
			else
			{
				max.Subtract(min);
				RetVal = new Integer(max, false, true);
				if (order == true)
					RetVal.isNegative = a.isNegative;
				else
					RetVal.isNegative = b.isNegative;
			}
			return RetVal;
		}

		public static Integer operator -(Integer a, int b)
		{
			Integer RetVal;
			bool bIsNegative = b < 0;
			b = System.Math.Abs(b);
			if (a.isNegative != bIsNegative)
			{
				BitManager bits = new BitManager(a.bitManager);
				bits.Add(b);
				RetVal = new Integer(bits, false, true);
				RetVal.isNegative = a.isNegative;
			}
			else if (a.bitManager == b)
			{
				return Integer.Zero;
			}
			else if (a.bitManager > b)
			{
				BitManager bits = new BitManager(a.bitManager);
				bits.Subtract(b);
				RetVal = new Integer(bits, false, true);
				RetVal.isNegative = a.isNegative;
			}
			else
			{
				BitManager bits = new BitManager(1);
				bits[0] = b;
				bits.Subtract(a.bitManager);
				RetVal = new Integer(bits, false, true);
				RetVal.isNegative = !a.isNegative;
			}
			return RetVal;
		}

		public static Integer operator -(Integer a, long b)
		{
			Integer RetVal;
			bool bIsNegative = b < 0;
			b = System.Math.Abs(b);
			if (a.isNegative != bIsNegative)
			{
				BitManager bits = new BitManager(a.bitManager);
				bits.Add(b);
				RetVal = new Integer(bits, false, true);
				RetVal.isNegative = a.isNegative;
			}
			else if (a.bitManager == b)
			{
				return Integer.Zero;
			}
			else if (a.bitManager > b)
			{
				BitManager bits = new BitManager(a.bitManager);
				bits.Subtract(b);
				RetVal = new Integer(bits, false, true);
				RetVal.isNegative = a.isNegative;
			}
			else
			{
				BitManager bits = new BitManager(2);
				bits.Add(b);
				bits.Subtract(a.bitManager);
				RetVal = new Integer(bits, false, true);
				RetVal.isNegative = !a.isNegative;
			}
			return RetVal;
		}

		public static Integer operator -(Integer a, Integer b)
		{
			BitManager max, min;
			long exponent;
			bool order = Integer.Sort(a, b, out max, out min, out exponent);

			Integer RetVal;
			if (a.isNegative != b.isNegative)
			{
				max.Add(min);
				RetVal = new Integer(max, false, true);
				RetVal.isNegative = a.isNegative;
			}
			else if (a.bitManager == b.bitManager)
			{
				return Integer.Zero;
			}
			else
			{
				max.Subtract(min);
				RetVal = new Integer(max, false, true);
				if (order == true)
					RetVal.isNegative = a.isNegative;
				else
					RetVal.isNegative = b.isNegative;
			}
			return RetVal;
		}

		public static Integer operator *(Integer a, int b)
		{
			BitManager bits = new BitManager(a.bitManager);
			bits.Multiply(System.Math.Abs(b));
			Integer RetVal = new Integer(bits, false, true);
			RetVal.isNegative = a.isNegative != (b < 0);
			return RetVal;
		}

		public static Integer operator *(Integer a, long b)
		{
			BitManager bits = new BitManager(a.bitManager);
			bits.Multiply(System.Math.Abs(b));
			Integer RetVal = new Integer(bits, false, true);
			RetVal.isNegative = a.isNegative != (b < 0);
			return RetVal;
		}

		public static Integer operator *(Integer a, Integer b)
		{

			BitManager bits = new BitManager(a.bitManager);
			bits.Multiply(b.bitManager);
			Integer RetVal = new Integer(bits, false, false);
			RetVal.exponent = a.exponent + b.exponent;
			RetVal.isNegative = a.isNegative != b.isNegative;
			RetVal.TrimTrailingWords();
			return RetVal;
		}

		public static Integer operator /(Integer a, Integer b)
		{
			if (a.exponent < b.exponent)
				return Integer.Zero;
			BitManager bm = new BitManager(a.bitManager);
			int exponent = a.exponent;
			if (exponent > b.exponent)
			{
				bm.LLS((int)(exponent-b.exponent)*BitManager.WordSize);
				exponent = b.exponent;
			}
			BitManager r;
			bm.Divide(b.bitManager, out r);
			Integer RetVal = new Integer(bm, false, false);
			RetVal.isNegative = a.isNegative != b.isNegative;
			RetVal.exponent = exponent;
			RetVal.TrimTrailingWords();
			return RetVal;
		}

		public static Integer operator /(Integer a, int b)
		{
			BitManager bm = new BitManager(a.bitManager);
			int r;
			bm.Divide(System.Math.Abs(b), out r);
			Integer RetVal = new Integer(bm, false, true);
			RetVal.isNegative = a.isNegative != (b < 0);
			return RetVal;
		}

		public static Integer operator /(Integer a, long b)
		{
			BitManager bm = new BitManager(a.bitManager);
			long r;
			bm.Divide(System.Math.Abs(b), out r);
			Integer RetVal = new Integer(bm, false, true);
			RetVal.isNegative = a.isNegative != (b < 0);
			return RetVal;
		}

		public static Integer operator %(Integer a, Integer b)
		{
			Integer RetVal;
			Integer.Divide(a, b, out RetVal);
			return RetVal;
		}

		public static int operator %(Integer a, int b)
		{
			BitManager bm = new BitManager(a.bitManager);
			int r;
			bm.Divide(System.Math.Abs(b), out r);
			if (a.isNegative != (b < 0))
				r *= -1;
			return r;
		}

		public static long operator %(Integer a, long b)
		{
			BitManager bm = new BitManager(a.bitManager);
			long r;
			bm.Divide(System.Math.Abs(b), out r);
			if (a.isNegative != (b < 0))
				r *= -1;
			return r;
		}
		#endregion
		#endregion

		#region Parsing
		public static Integer Parse(string text) { return Integer.Parse(text, null, null); }
		public static Integer Parse(string text, string format) { return Integer.Parse(text, format, null); }
		public static Integer Parse(string text, IFormatProvider formatProvider) { return Integer.Parse(text, null, formatProvider); }

		public static bool TryParse(string text, out Integer value) { return Integer.TryParse(text, null, null, out value); }
		public static bool TryParse(string text, string format, out Integer value) { return Integer.TryParse(text, format, null, out value); }
		public static bool TryParse(string text, IFormatProvider formatProvider, out Integer value) { return Integer.TryParse(text, null, formatProvider, out value); }

		public static bool TryParse(string text, string format, IFormatProvider formatProvider, out Integer value)
		{
			try
			{
				value = Integer.Parse(text, format, formatProvider);
				return true;
			}
			catch
			{
				value = null;
				return false;
			}
		}

		public static Integer Parse(string text, string format, IFormatProvider formatProvider)
		{
			BigNumberFormatInfo nfi = BigNumberFormatInfo.GetInstance(formatProvider);
			if (string.IsNullOrEmpty(format))
				format = "g";
			text = text.Trim();
			char specifier = char.ToLower(format[0]);
			StringBuilder sb = new StringBuilder(text);
			bool isNegative = text.StartsWith(nfi.NumberFormatInfo.NegativeSign);
			int baseSeparatorIndex = text.IndexOf(nfi.BaseSeparator);
			int eIndex = text.IndexOfAny(new char[] { 'e', 'E' });
			if (eIndex > -1)
			{
				string sign = nfi.NumberFormatInfo.PositiveSign;
				if (eIndex > text.Length - 1 - sign.Length || text.Substring(eIndex + 1, sign.Length) != sign)
					eIndex = -1;
			}

			if (baseSeparatorIndex > -1)
			{
				if (baseSeparatorIndex == 0 || baseSeparatorIndex == text.Length - 1)
				{
					throw new FormatException(string.Format(
						"The text \"{0}\" contains the BigNumberFormatInfo.BaseSeparator \'{1}\' but no base value.",
						text, nfi.BaseSeparator));
				}
				if (specifier == 'd' || specifier == 'b' || specifier == 'x')
				{
					throw new FormatException(string.Format(
						"The format \"{0}\" already defines the base, thus the text \"{1}\" which also contains base information is not compatible with this format.",
						format, text));
				}
			}
			if (eIndex > -1)
			{
				if (!(specifier == 'g' || specifier == 'e'))
				{
					throw new FormatException(string.Format(
						"The text \"{0}\" contains parts of a scientific notation (\"{1}\"), but the format is neither \"g\" nor \"e\".",
						text, text[eIndex] + nfi.NumberFormatInfo.PositiveSign));
				}
				if (baseSeparatorIndex > -1)
				{
					throw new FormatException(string.Format(
						"The text \"{0]\" contains parts of a scientific notation (\"{1}\"), but also contains the BigNumberFormatInfo.BaseSeparator \'{2}\'.",
						text, text[eIndex] + nfi.NumberFormatInfo.PositiveSign, nfi.BaseSeparator));
				}
				if (eIndex > text.Length - 2 - nfi.NumberFormatInfo.PositiveSign.Length)
				{
					throw new FormatException(string.Format(
						"The text \"{0}\" contains parts of a scientific notation (\"{1}\"), but no value.",
						text, text[eIndex] + nfi.NumberFormatInfo.PositiveSign));
				}
				specifier = 'e';
			}
			if (isNegative == true)
			{
				sb.Remove(0, 1);
				baseSeparatorIndex--;
				eIndex--;
			}
			int b = 0;
			Integer powerOf10 = null;

			if (format.ToLowerInvariant().StartsWith("base"))
			{
				if (int.TryParse(format.Substring(4), out b) == false)
					throw new FormatException(string.Format("Value of base could not be parsed from the format \"{0}\".", format));
			}
			else if (specifier == 'd')
			{
				b = 10;
			}
			else if (specifier == 'b')
			{
				b = 2;
			}
			else if (specifier == 'x')
			{
				b = 16;
			}
			else if (specifier == 'e')
			{
				b = 10;
				if (eIndex > -1)
				{
					int val;
					int i = eIndex + 1 + nfi.NumberFormatInfo.PositiveSign.Length;
					if (int.TryParse(sb.ToString(i, sb.Length - i), out val) == false)
						throw new FormatException(string.Format("Power of 10 cannot be parsed from the text \"{0}\".", text));
					powerOf10 = Integer.Power(10, val);
					sb.Remove(eIndex, sb.Length - eIndex);
				}
			}
			else if (baseSeparatorIndex < 0)
			{
				b = nfi.Base;
			}
			else
			{
				int nB;
				if (nfi.BasePattern == 0)
				{
					nB = int.Parse(sb.ToString(0, baseSeparatorIndex), nfi);
					sb.Remove(0, baseSeparatorIndex + 1);
				}
				else
				{
					nB = int.Parse(sb.ToString(baseSeparatorIndex + 1, sb.Length - baseSeparatorIndex - 1), nfi);
					sb.Remove(baseSeparatorIndex, sb.Length - baseSeparatorIndex);
				}
				if (b != 0 && b != nB)
				{
					throw new FormatException(string.Format("The text \"{0}\" and the format \"{1}\" define different bases.", text, format));
				}
				b = nB;
			}

			sb.Replace(nfi.NumberFormatInfo.NumberGroupSeparator, string.Empty);

			Integer RetVal = Integer.ParseBaseX(sb, nfi, b);
			if (powerOf10 != null)
				RetVal.bitManager.Multiply(powerOf10.bitManager);
			RetVal.isNegative = isNegative;
			RetVal.TrimTrailingWords();
			return RetVal;
		}

		private static Integer ParseBaseX(StringBuilder text, BigNumberFormatInfo nfi, int b)
		{
			if (b < 2)
				throw new ArgumentOutOfRangeException("b", "Value must be greater than 1.");

			if (b == 2)
				return Integer.ParseBase2(text, nfi);
			if (b == 10)
				return Integer.ParseBase10(text, nfi);
			int power = Integer.PowerOf2(b);
			if (power > -1)
				return Integer.ParseBasePowerOf2(text, nfi, power);

			BitManager bmBase = BitManager.From32Bits(b);
			BitManager bmCurrentBase = BitManager.From32Bits(1);
			Integer RetVal = 0;
			if (b < 37)
			{
				for (int i = text.Length - 1; i > -1; i--)
				{
					if (char.IsLetterOrDigit(text[i]) == false)
						throw new FormatException(string.Format("Invalid char \'{0}\' in text \"{1}\". Only letters and digits are allowed.", text[i], text));

					int v;
					if (char.IsDigit(text[i]))
						v = (int)text[i] - 48;
					else if (char.IsLower(text[i]))
						v = (int)text[i] - 87;
					else
						v = (int)text[i] - 55;
					if (v >= b)
					{
						throw new FormatException(string.Format(
							"The char \'{0}\' represents the value {1} which is outside the allowed range for base {2}.", text[i], v, b));
					}
					BitManager val = BitManager.From32Bits(v);
					val.Multiply(bmCurrentBase);
					RetVal.bitManager.Add(val);
					bmCurrentBase.Multiply(bmBase);
				}
			}
			else
			{
				string[] digits = text.ToString().Split(new string[] { nfi.DigitSeparator }, StringSplitOptions.None);
				for (int i = digits.Length - 1; i > -1; i--)
				{
					BitManager val = BitManager.From32Bits(int.Parse(digits[i], nfi));
					val.Multiply(bmCurrentBase);
					RetVal.bitManager.Add(val);
					bmCurrentBase.Multiply(bmBase);
				}
			}
			return RetVal;
		}

		private static Integer ParseBase10(StringBuilder text, BigNumberFormatInfo nfi)
		{
			Integer RetVal = 0;
			BitManager b10 = Integer.Base10.bitManager;
			BitManager bmCurrentBase = BitManager.From32Bits(1);
			int length = Integer.Base10DigitLength;
			int index = text.Length;
			while (index > 0)
			{
				int nIndex = System.Math.Max(0, index - length);
				length = index - nIndex;
				index = nIndex;
				BitManager val = BitManager.From32Bits(int.Parse(text.ToString(index, length), nfi));
				val.Multiply(bmCurrentBase);
				RetVal.bitManager.Add(val);
				bmCurrentBase.Multiply(b10);
			}
			return RetVal;
		}

		private static Integer ParseBase2(StringBuilder text, BigNumberFormatInfo nfi)
		{
			Integer RetVal = 0;
			for (int i = 0; i < text.Length; i++)
			{
				if (text[i] == '1')
					RetVal.bitManager.Insert(true);
				else if (text[i] == '0')
					RetVal.bitManager.Insert(false);
				else
					throw new FormatException(string.Format("Invalid char \'{0}\' in text \"{1}\". Only '1' and '0' are allowed.", text[i], text));
			}
			return RetVal;
		}

		private static Integer ParseBasePowerOf2(StringBuilder text, BigNumberFormatInfo nfi, int power)
		{
			Integer RetVal = 0;
			int b = 1 << power;
			if (b < 37)
			{
				for (int i = 0; i < text.Length; i++)
				{
					if (char.IsLetterOrDigit(text[i]) == false)
						throw new FormatException(string.Format("Invalid char \'{0}\' in text \"{1}\". Only letters and digits are allowed.", text[i], text));

					int val;
					if (char.IsDigit(text[i]))
						val = (int)text[i] - 48;
					else if (char.IsLower(text[i]))
						val = (int)text[i] - 87;
					else
						val = (int)text[i] - 55;

					if (val >= b)
					{
						throw new FormatException(string.Format(
							"The char \'{0}\' represents the value {1} which is outside the allowed range for base {2}.", text[i], val, b));
					}
					val <<= BitManager.WordSize - power;
					RetVal.bitManager.Insert(val, power);
				}
			}
			else
			{
				string[] digits = text.ToString().Split(new string[] { nfi.DigitSeparator }, StringSplitOptions.None);
				for (int i = 0; i < digits.Length; i++)
				{
					int val = int.Parse(digits[i], nfi);
					val <<= BitManager.WordSize - power;
					RetVal.bitManager.Insert(val, power);
				}
			}
			return RetVal;
		}
		#endregion

		#region Implicit Casts
		public static implicit operator Integer(int i) { return new Integer(i); }
		public static implicit operator Integer(long l) { return new Integer(l); }

		public static implicit operator Integer(uint i)
		{
			BitManager bm = new BitManager(1);
			bm[0] = (int)i;
			return new Integer(bm, true, false);
		}

		public static implicit operator Integer(ulong l)
		{
			BitManager bm = new BitManager(2);
			bm.Add((long)l);
			return new Integer(bm, true, true);
		}
		#endregion

		#region Explicit Casts

		#endregion
		#endregion
		#endregion

		#region Instance
		#region Fields
		BitManager bitManager;
		int signAndExponent;
		#endregion

		#region Properties
		bool isNegative
		{
			get { return ((uint)this.signAndExponent >> 31) == 1u; }
			set
			{
				int mask = 1 << 31;
				if (value == true)
					this.signAndExponent |= mask;
				else
					this.signAndExponent &= ~mask;
			}
		}

		int exponent
		{
			get { return (this.signAndExponent & Integer.ExponentMask); }
			set { this.signAndExponent = (this.signAndExponent & ~Integer.ExponentMask) | (value & Integer.ExponentMask); }
		}
		#endregion

		#region Constructors
		Integer(int signAndExponent, BitManager bitManager, bool trimLeadingZeros, bool trimTrailingZeros)
		{
			this.isNegative = isNegative;
			if (bitManager == null)
			{
				this.bitManager = new BitManager();
				this.isNegative = false;
			}
			else
			{
				this.bitManager = bitManager;
				if (trimLeadingZeros)
					this.TrimLeadingWords();
				if (trimTrailingZeros)
					this.TrimTrailingWords();
			}
		}

		Integer(BitManager bitManager, bool removeLeadingZeros, bool trimTrailingZeros)
			: this(0, bitManager, removeLeadingZeros, trimTrailingZeros) { }

		public Integer(IEnumerable<int> words, int exponent, bool isNegative)
			: this(0, new BitManager(words), true, false)
		{
			this.isNegative = isNegative;
			if (exponent < Integer.MinExponent || exponent > Integer.MaxExponent)
				throw new ArgumentOutOfRangeException("exponent");
			this.exponent = exponent;
			this.TrimTrailingWords();
		}

		public Integer(IEnumerable<int> words)
			: this(words, 0, false) { }

		public Integer(Integer value)
			: this(value.signAndExponent, new BitManager(value.bitManager), false, false) { }

		public Integer(int value)
			: this(new BitManager(1), false, false)
		{
			if (value < 0)
			{
				this.isNegative = true;
			}
			if (value == int.MinValue)
			{
				this.bitManager[0] = int.MaxValue;
				this.bitManager.Add(1);
			}
			else
			{
				this.bitManager[0] = System.Math.Abs(value);
			}
			this.TrimLeadingWords();
			this.TrimTrailingWords();
		}

		public Integer(long value)
			: this(new BitManager(2), false, false)
		{
			if (value < 0)
			{
				this.isNegative = true;
			}
			if (value == long.MinValue)
			{
				this.bitManager.Add(long.MaxValue);
				this.bitManager.Add(1);
			}
			else
			{
				this.bitManager.Add(System.Math.Abs(value));
			}
			this.bitManager.Add(value);
			this.TrimLeadingWords();
			this.TrimTrailingWords();
		}

		public Integer(int[] bits)
			:this(bits.Last(), new BitManager(bits.Length-1), false, false)
		{
			for (int i = 0; i < bits.Length-1; i++)
				this.bitManager[i] = bits[i];
			this.TrimLeadingWords();
			this.TrimTrailingWords();
		}
		#endregion

		#region Methods
		#region Private
		void Increment()
		{
			if (this.isNegative)
			{
				this.bitManager.Subtract(1, 0);
				this.bitManager.TrimLeadingWords();
				if (this.bitManager == 0)
					this.isNegative = false;
			}
			else
			{
				this.bitManager.Add(1, 0);
			}
		}

		void Decrement()
		{
			if (this.isNegative)
			{
				this.bitManager.Add(1, 0);
			}
			else if (this.bitManager == 0)
			{
				this.bitManager.Add(1, 0);
				this.isNegative = true;
			}
			else
			{
				this.bitManager.Subtract(1, 0);
				this.bitManager.TrimLeadingWords();
			}
		}

		void TrimLeadingWords()
		{
			this.bitManager.TrimLeadingWords();
			if (this.bitManager.Length == 0)
				this.signAndExponent = 0;
		}

		void TrimTrailingWords()
		{
			int count = this.bitManager.TrimTrailingWords();
			if (this.bitManager.Length == 0)
			{
				this.signAndExponent = 0;
				return;
			}
			count += (int)this.exponent;
			if (count > Integer.MaxExponent)
				throw new OverflowException();
			else
				this.exponent = count;
		}
		#endregion

		#region Public
		public int[] GetBits()
		{
			int[] RetVal = new int[this.bitManager.Length + 1];
			this.bitManager.CopyTo(RetVal, 0);
			RetVal[RetVal.Length - 1] = this.signAndExponent;
			return RetVal;
		}
		#endregion

		#region ToString
		public override string ToString() { return this.ToString(null, null); }
		public string ToString(string format) { return this.ToString(format, null); }
		public string ToString(IFormatProvider formatProvider) { return this.ToString(null, formatProvider); }

		public string ToString(string format, IFormatProvider formatProvider)
		{
			BigNumberFormatInfo nfi = BigNumberFormatInfo.GetInstance(formatProvider);

			if (string.IsNullOrEmpty(format))
				format = "g";

			StringBuilder sb;

			char specifier = char.ToLower(format[0]);

			int b;
			int minLength = 0;

			if (format.ToLowerInvariant().StartsWith("base"))
			{
				if (int.TryParse(format.Substring(4), out b) == false)
					throw new FormatException(string.Format("Value of base could not be parsed from the format \"{0}\".", format));
				sb = this.ToStringBaseX(b, nfi, char.IsLower(format[0]));

				if (minLength == 0)
					minLength = 1;
				if (sb.Length < minLength)
					sb.Insert(0, new string('0', minLength - sb.Length));

				if (nfi.BasePattern == 0)
				{
					sb.Insert(0, nfi.BaseSeparator);
					sb.Insert(0, b.ToString(nfi));
				}
				else
				{
					sb.Append(nfi.BaseSeparator);
					sb.Append(b.ToString(nfi));
				}
			}
			else
			{
				if (format.Length > 1)
				{
					if (int.TryParse(format.Substring(1), out minLength) == false)
						throw new FormatException(string.Format("Mininum digit count could not be parsed from format \"{0}\".", format));
				}

				if (specifier == 'b')
					b = 2;
				else if (specifier == 'x')
					b = 16;
				else if (specifier == 'd' || specifier == 'e')
					b = 10;
				else
					b = nfi.Base;

				sb = this.ToStringBaseX(b, nfi, char.IsLower(format[0]));

				if (specifier == 'e')
				{
					if (sb.Length > 1)
					{
						if (minLength == 0)
						{
							minLength = sb.Length;
							while (minLength > 0)
							{
								if (sb[minLength - 1] != '0')
									break;
								minLength--;
							}
						}
						int powOf10 = sb.Length - 1;
						if (sb.Length > minLength)
							sb.Remove(minLength, sb.Length - minLength);
						if (sb.Length > 1)
							sb.Insert(1, nfi.NumberFormatInfo.NumberDecimalSeparator);
						sb.Append(format[0]);
						sb.Append(nfi.NumberFormatInfo.PositiveSign);
						sb.Append(powOf10.ToString(nfi));
					}
				}
				else
				{
					if (minLength == 0)
						minLength = 1;

					if (sb.Length < minLength)
						sb.Insert(0, new string('0', minLength - sb.Length));

					if (specifier == 'n')
					{
						int index = sb.Length - nfi.NumberFormatInfo.NumberGroupSizes[0];
						int iGroupeSizes = 0;
						while (index > 0)
						{
							sb.Insert(index, nfi.NumberFormatInfo.NumberGroupSeparator);
							if (iGroupeSizes + 1 < nfi.NumberFormatInfo.NumberGroupSizes.Length && nfi.NumberFormatInfo.NumberGroupSizes[iGroupeSizes + 1] != 0)
								iGroupeSizes++;
							index -= nfi.NumberFormatInfo.NumberGroupSizes[iGroupeSizes];
						}
					}
				}
			}

			if (this.isNegative)
				sb.Insert(0, nfi.NumberFormatInfo.NegativeSign);
			return sb.ToString();
		}

		private StringBuilder ToStringBase10(BigNumberFormatInfo nfi)
		{
			BitManager val = new BitManager(this.bitManager);
			val.LLS((int)this.exponent * BitManager.WordSize);
			BitManager div = Integer.Base10.bitManager;
			StringBuilder sb = new StringBuilder();
			string f = 'd' + Integer.Base10DigitLength.ToString(NumberFormatInfo.InvariantInfo);
			while (val >= div)
			{
				BitManager remainder;
				val.Divide(div, out remainder);
				sb.Insert(0, remainder[0].ToString(f, nfi));
			}
			sb.Insert(0, val[0].ToString(nfi));
			return sb;
		}

		private StringBuilder ToStringBaseX(int b, BigNumberFormatInfo nfi, bool lowerCase)
		{
			if (b < 2)
				throw new ArgumentOutOfRangeException("b");

			if (b == 2)
				return this.ToStringBase2(nfi);
			else if (b == 16)
				return this.ToStringBase16(nfi, lowerCase);
			else if (b == 10)
				return this.ToStringBase10(nfi);

			StringBuilder sb;
			int powerOf2 = Integer.PowerOf2(b);
			if (powerOf2 > 0)
			{
				sb = this.ToStringBasePowerOf2(powerOf2, nfi, lowerCase);
			}
			else
			{
				sb = new StringBuilder();
				BitManager val = new BitManager(this.bitManager);
				val.LLS((int)this.exponent * BitManager.WordSize);
				BitManager div = new Integer(b).bitManager;
				if (b < 37)
				{
					while (val > 0)
					{
						BitManager remainder;
						val.Divide(div, out remainder);
						int v = remainder[0];
						if (v < 10)
							v += 48;
						else
						{
							if (lowerCase == true)
								v += 87;
							else
								v += 55;
						}
						sb.Insert(0, (char)v);
					}
				}
				else
				{
					while (val >= div)
					{
						BitManager remainder;
						val.Divide(div, out remainder);
						sb.Insert(0, remainder[0].ToString(nfi));
						sb.Insert(0, nfi.DigitSeparator);
					}
					sb.Insert(0, val[0].ToString(nfi));
				}
			}
			return sb;
		}

		private static int PowerOf2(int i)
		{
			if (i == 0)
				return -1;
			int val = 0;
			uint b = (uint)i;
			while ((b & 1) == 0)
			{
				b >>= 1;
				val++;
			}
			b >>= 1;
			if (b != 0)
				return -1;
			return val;
		}

		private StringBuilder ToStringBasePowerOf2(int power, BigNumberFormatInfo nfi, bool lowerCase)
		{
			if (power == 1)
				return this.ToStringBase2(nfi);
			if (power == 4)
				return this.ToStringBase16(nfi, lowerCase);

			StringBuilder sb = new StringBuilder();
			BitManager val = new BitManager(this.bitManager);
			val.LLS((int)this.exponent * BitManager.WordSize);
			int mask = (int)((~0u) >> (32 - power));
			if ((1 << power) < 37)
			{
				for (int i = 0; i < this.bitManager.Length * Integer.WordSize / power; i++)
				{
					int v = val[0] & mask;
					if (v < 10)
						v += 48;
					else
					{
						if (lowerCase == true)
							v += 87;
						else
							v += 55;
					}
					sb.Insert(0, (char)v);
					val.LRS(power);
				}
				while (sb.Length > 1 && sb[0] == '0')
					sb.Remove(0, 1);
			}
			else
			{
				int v = val[0] & mask;
				sb.Append(v.ToString(nfi));
				for (int i = 1; i < this.bitManager.Length * Integer.WordSize / power; i++)
				{
					val.LRS(power);
					v = val[0] & mask;
					sb.Insert(0, nfi.DigitSeparator);
					sb.Insert(0, v.ToString(nfi));
				}
			}
			return sb;
		}

		private StringBuilder ToStringBase2(BigNumberFormatInfo nfi)
		{
			StringBuilder sb = new StringBuilder();
			int mask = 1 << 31;
			for (int i = this.bitManager.Length - 1; i > -1; i--)
			{
				int v = this.bitManager[i];
				for (int bit = 0; bit < 32; bit++)
				{
					if ((v & mask) == mask)
						sb.Append('1');
					else if (sb.Length > 0)
						sb.Append('0');
					v = v << 1;
				}
			}
			if (this.exponent > 0)
			{
				sb.Append(new string('0', (int)this.exponent * BitManager.WordSize));
			}
			return sb;
		}

		private StringBuilder ToStringBase16(BigNumberFormatInfo nfi, bool lowerCase)
		{
			string format;
			if (lowerCase == true)
				format = "x";
			else
				format = "X";
			StringBuilder sb = new StringBuilder();
			sb.Append(this.bitManager[this.bitManager.Length-1].ToString(format, nfi));
			format += "8";
			for (int i = this.bitManager.Length - 2; i > -1; i--)
			{
				sb.Append(this.bitManager[i].ToString(format, nfi));
			}
			if (this.exponent > 0)
			{
				sb.Append(new string('0', (int)this.exponent * BitManager.WordSize / 4));
			}
			return sb;
		}
		#endregion
		#endregion
		#endregion

		#region IScalar
		bool IScalar.IsEqualTo(IScalar scalar)
		{
			return (this == (Integer)scalar);
		}

		IScalar IScalar.Divide(IScalar scalar)
		{
			return (this / (Integer)scalar);
		}

		IScalar IScalar.Subtract(IScalar scalar)
		{
			return (this - (Integer)scalar);
		}

		IScalar IScalar.Multiply(IScalar scalar)
		{
			return (this * (Integer)scalar);
		}

		IScalar IScalar.Add(IScalar scalar)
		{
			return (this + (Integer)scalar);
		}

		IOperand IOperand.GetDeepCopy()
		{
			return new Integer(this);
		}
		#endregion

		#region ILinearScalar
		bool ILinearScalar.IsSmallerThan(ILinearScalar scalar)
		{
			return (this < (Integer)scalar);
		}

		bool ILinearScalar.IsGreaterThan(ILinearScalar scalar)
		{
			return (this > (Integer)scalar);
		}

		int IComparable.CompareTo(object obj)
		{
			Integer integer = (Integer)obj;
			if (integer == this)
				return 0;
			if (integer < this)
				return -1;
			return 1;
		}
		#endregion

		#region Subtypes
		public class WordCollection : IntIndexedPropertyGet<int>
		{
			Integer integer;

			public WordCollection(Integer integer)
			{
				if (integer == null)
					throw new ArgumentNullException();
				this.integer = integer;
			}

			public override int Count { get { return this.integer.bitManager.Length; } }
			public override int this[int index] { get { return this.integer.bitManager[index]; } }
		}

		public class BitCollection : IntIndexedPropertyGet<bool>
		{
			Integer integer;

			public BitCollection(Integer integer)
			{
				if (integer == null)
					throw new ArgumentNullException();
				this.integer = integer;
			}

			public override int Count { get { return this.integer.bitManager.BitLength; } }
			public override bool this[int index] { get { return this.integer.bitManager.Bits[index]; } }
		}
		#endregion
	}
}
